package code1.string;

import java.util.Arrays;

/**
 * 原题链接：https://leetcode.cn/problems/reverse-words-in-a-string/
 */
public class P151 {

    //删除多余的空格
    public static String removeSpace(char[] str){
        int slowIndex=0,fastIdnex=0;        //快慢指针
        //去掉字符串前面的空格
        while (str.length>0 && fastIdnex<str.length && str[fastIdnex]==' '){
            fastIdnex++;
        }
        //去掉中间部分冗余的空格
        for(;fastIdnex<str.length;fastIdnex++){
            if(fastIdnex-1>0 && str[fastIdnex-1]==str[fastIdnex] && str[fastIdnex]==' ' ){
                continue;
            }else{
                str[slowIndex++]=str[fastIdnex];
            }
        }
        //去掉字符串后面的空格
        int newSize=0;
        if(slowIndex-1>0 && str[slowIndex-1]==' '){
            newSize=slowIndex-1;
        }else{
            newSize=slowIndex;
        }
        char[] res=new char[newSize];
        for(int i=0;i<res.length;i++){
            res[i]=str[i];
        }
        return String.valueOf(res);
    }

    //翻转整个字符串
    public static String reverseAll(String s){
        char[] str = s.toCharArray();
        for(int i=0,j=str.length-1;i<j;i++,j--){
            str[i]^=str[j];
            str[j]^=str[i];
            str[i]^=str[j];
        }
        StringBuilder sb=new StringBuilder();
        return String.valueOf(str);
    }

    //翻转每个单词
    public static String reverseEach(String s){
        StringBuilder sb=new StringBuilder();
        int start=0,end=1;
        int length=s.length();
        while (start < length){
            //找到单词的结束为止
            while(end<length && s.charAt(end)!=' '){
                end++;
            }
            if(end==length){
                sb.append(reverseAll(s.substring(start,end)));
            }else{
                sb.append(reverseAll(s.substring(start,end))).append(" ");
            }
            start=end+1;
            end=start+1;
        }
        return sb.toString();
    }

    //方法1
    public static String reverseWords(String s) {
        //1.去除多余的空格
        String s1 = removeSpace(s.toCharArray());
        //2.翻转整个字符串
        String s2 = reverseAll(s1);
        //3.翻转每个单词
        String s3 = reverseEach(s2);
        return s3;
    }

    public static void main(String[] args) {
        System.out.println(reverseWords("  hello world  "));
    }

    //split法
    public String reverseWords2(String s) {
        String[] strings = s.trim().split("\\s+");      //trim去除字符串两端的空格
        StringBuilder sb=new StringBuilder();
        for(int i=strings.length-1;i>0;i--){
            sb.append(strings[i]).append(" ");
        }
        sb.append(strings[0]);
        return sb.toString();
    }
}
